package leetcode每日一题;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 最大矩形面积 {
    public static void main(String[] args) {

    }

    /**
     * 将问题转化为求柱形图的最大面积 (参看 leetcode 84题)
     * 我们将上述的二维数组转化为柱子，举个例子
     *      {
     *          {1，1，0，0}，
     *          {1，0，1，0}
     *      }
     * 此时的第一行的柱形图：
     *      1  0  1  0 (柱子的高度)
     * 第二行的柱形图：
     *      2  0  1  0 (柱子的高度)
     * 从上面可知我们需要两个辅助函数
     *  1. 求出当前行为底边的柱子的最大面积 参数时当前的高度数组
     *  2. 求出当前行为底边的每个柱子的高度，即以当前行的第j个元素为起始向上的最大连续1高度
     *     如果起始元素为0，则高度为0
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) {return 0;} // 空数组
        int maxarea = 0; // 记录最大面积
        for(int i = 0; i < matrix.length; i++) { // 扫描行
            int[] heights = new int[matrix[i].length]; // 记录当前行为底部的柱形图的高度数组
            for(int j = 0; j < matrix[i].length; j++) {
                heights[j] = maxContinuelenByCol(matrix,i,j);
            }
            maxarea = Math.max(maxarea,largestRectangleArea(heights));
        }
        return maxarea;
    }
    public static int maxContinuelenByCol(char[][] matrix,int row,int col) {
        if(matrix[row][col] == '0') {
            return 0;
        }
        int height = 0;
        while(matrix[row][col] == '1') {
            height++;
            row--;
            if(row == -1) {
                break;
            }
        }
        return height;
    }
    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0) {
            return 0;
        }
        if(heights.length == 1) {
            return heights[0];
        }
        int maxarea = 0; // 记录最大面积
        // 扫描柱子的高度
        for(int i = 0; i < heights.length; i++) {
            if(i == 0) {
                int width = 1;
                int right = i+1;
                while(heights[right] >= heights[i] && right < heights.length) {
                    width++;
                    right++;
                    if(right == heights.length) {
                        break;
                    }
                }
                // 退出循环时找到了最大的宽度
                maxarea = Math.max(maxarea,width*heights[i]);
            }
            else if(i == heights.length-1) {
                int width = 1;
                int left = i-1;
                while(heights[left] >= heights[i] && left >= 0) {
                    width++;
                    left--;
                    if(left == -1) {
                        break;
                    }
                }
                // 循环退出找到了最大的宽度
                maxarea = Math.max(maxarea,width*heights[i]);
            }
            else {
                // 中间的柱子
                int width = 1;
                int left = i-1;
                int right = i+1;
                while(heights[left] >= heights[i] && left >= 0) {
                    width++;
                    left--;
                    if(left == -1) {
                        break;
                    }
                }
                while(heights[right] >= heights[i] && right < heights.length) {
                    width++;
                    right++;
                    if(right == heights.length) {
                        break;
                    }
                }
                maxarea = Math.max(maxarea,width*heights[i]);
            }
        }
        return maxarea;
    }









    /****************************************错误代码（及出错的分析）**************************************/
    /**
     * 下面的代码有逻辑错误
     * 我的思路是：找出以当前行为边的最大矩形
     * 具体的过程：
     *      找出当前边的所有连续1的宽度，然后利用木桶原理，找到对应的连续宽的每一列的最小连续1的长
     * 但是这样做有一个问题：
     *      直接上例子：
               1 1 1 1 1 1 1 1
               1 1 1 1 1 1 1 0
               1 1 1 1 1 1 1 0
               1 1 1 1 1 0 0 0
               0 1 1 1 1 0 0 0


               1 1 1 0 1 1 1 1
               1 1 1 1 1 1 1 0
               1 1 1 1 1 1 1 0
               1 1 1 1 1 0 0 0
               0 1 1 1 1 0 0 0
     *      按照上述思路明显是有问题的，因为一旦跳过当前行，考虑下一行的时候就完全忽略了上一行于下一行
     *      之间的联系
     *      计算出的面积就不一定是最大的，而是当前行为起始行的矩阵的最大面积，是一个局部最优解，但不一
     *      定是全局最优解
     *
     *      如何找到第i行以下的矩形和第i-1行以下的矩形的最大面积之间的关系，此时可能会考虑动态规划算法
     *      设置dp数组 dp[i]: 表示第i行为起始行的矩阵的最大面积
     *      dp[i-1] > dp[i] 因为以第i-1行为起始行的矩阵包含以第i行为起始行的矩阵，所以我们从最后一行
     *      向第一行进行dp顺序，最后的全局最优解就是 dp[0]
     *
     *      思考dp[i-1]于dp[i] 之间的关系：
     *          dp[i-1]: 表示第i-1行为起始行的矩阵的最大面积
     *          dp[i]:  表示第i行为起始行的矩阵的最大面积
     *          之间相差一个第i-1行
     *      注意此时：不一定相差的就是第i-1行的最大面积，因为可能不连续，在中间中断了，如上面的第二个矩阵
     *      一维dp貌似不太好描述它们之间的关系
     *
     *      考虑二维dp dp[i][j]其含义：以第[i][j]为起点的矩阵的最大面积，还是从矩阵的最后一个元素向第一
     *      个元素开始dp
     *
     * @param matrix
     * @return
     */
    public static int maximalRectangle_Error(char[][] matrix) {
        int row = matrix.length; // 矩阵的行
        int col = matrix[0].length; // 矩阵的列
        int maxArea = 0; // 记录最大面积
        for(int i = 0; i < row; i++) { // 扫描行
            maxArea = Math.max(countMaxAreaByCurrrentRow_Error(matrix,i),maxArea);
        }
        return maxArea;
    }
    /**
     * 计算矩阵以当前行row为宽的可能的最大矩形面积
     * @param A
     * @param rowNo：当前行
     * @return：返回最大面积
     */
    public static int countMaxAreaByCurrrentRow_Error(char[][] matrix,int rowNo) {
        int maxarea = 0; // 记录最大面积
        // 扫描第rowNo行的所有元素
        for (int j = 0; j < matrix[rowNo].length; j++) {
            while (matrix[rowNo][j] == '0') {
                j++;
                if (j == matrix[rowNo].length) {
                    break;
                }
            }
            if (j == matrix[rowNo].length) {
                continue;
            }
            // 当前j指向的元素为1，找到以j为起始的连续最大为1的宽
            int width = 0;
            int start = j; // 记录当前的起始位置
            while (matrix[rowNo][j] == '1') {
                width++;
                j++;
                if (j == matrix[rowNo].length) {
                    break;
                }
            }
            // 找到了以j为起始的最长连续1的长度

            // 下面我们需要确定从j到j+width-1这些列中连续1最短的一个
            int minheight = Integer.MAX_VALUE;
            for (int k = start; k < start + width; k++) {
                // 计算第k列的连续1的长度
                int kheight = 0;
                int i = rowNo;
                while (matrix[i][k] == '1') {
                    kheight++;
                    i++;
                    if (i == matrix.length) {
                        break;
                    }
                }
                // 找到了当前第k行的连续最长1
                minheight = Math.min(minheight,kheight);
            }
            maxarea = Math.max(width*minheight,maxarea);
        }
        return maxarea;
    }

    /** 上面的代码没有编码问题，但是有逻辑问题，找不到最优解 */
    /**
     * 计算第row行的最大连续1宽
     * @param matrix
     * @param row
     * @return
     */
    public static int maxContinuelenByRow1(char[][] matrix,int row,int col) {
        int max = 0;
        for (int j = col; j < matrix[row].length; j++) {
            while (matrix[row][j] == '0') {
                j++;
                if (j == matrix[row].length) {
                    break;
                }
            }
            if (j == matrix[row].length) {
                break;
            }
            int cur = 0;
            while (matrix[row][j] == '1') {
                cur++;
                j++;
                if (j == matrix[row].length) {
                    break;
                }
            }
            max = Math.max(max,cur);
        }
        return max;
    }

    /**
     * 计算第col列的第row行以下的最长连续1
     * @param matrix
     * @param row
     * @param col
     * @return
     */
    public static int maxContinuelenByCol1(char[][] matrix,int row,int col) {
        int max = 0;
        for (int i = row; i < matrix.length; i++) {
            while (matrix[i][col-1] == '0') {
                i++;
                if (i == matrix.length) {
                    break;
                }
            }
            if (i == matrix.length) {
                break;
            }
            int cur = 0;
            while (matrix[i][col-1] == '1') {
                cur++;
                i++;
                if (i == matrix.length){
                    break;
                }
            }
        }
        return max;
    }
}
